package com.ayuer.chapter10;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class FloydWarShell {
    public static void main(String[] args) {

        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.edges = List.of(new Edge(v3, -2));
        v2.edges = List.of(new Edge(v1, 4), new Edge(v3, 3));
        v3.edges = List.of(new Edge(v4, 2));
        v4.edges = List.of(new Edge(v2, -1));

        LinkedList<Vertex> graph = new LinkedList<>(List.of(v1, v2, v3, v4));
        floydWarShell(graph);
    }

    /**
     *
     * @param graph
     */
    public static void floydWarShell(List<Vertex> graph) {
        int size = graph.size();
        //记录距离
        int[][] dist = new int[size][size];
        //记录路径
        Vertex[][] path = new Vertex[size][size];
//        print(dist);
        //初始化
        for (int i = 0; i < size; i++) {
            Vertex v = graph.get(i);
            Map<Vertex, Integer> map = v.edges.stream()
                    .collect(Collectors.toMap(e -> e.linked, e -> e.weight));
            for (int j = 0; j < size; j++) {
                Vertex u = graph.get(j);
                if (v == u) {
                    dist[i][j] = 0;
                } else {
                    //判断是否在edges转的map当中
                    dist[i][j] = map.getOrDefault(u, Integer.MAX_VALUE);
                    //存入当前节点的前驱节点
                    path[i][j] = map.get(u) != null ? v : null;
                }
            }
        }
        print(dist);

        print(path);
        // 借路
        //体现借多少轮，（元素个数）
        for (int k = 0; k < size; k++) {
            //体现row
            for (int i = 0; i < size; i++) {
                //体现column
                for (int j = 0; j < size; j++) {
                    //i行借k顶点到达j的顶点
                    int distRes = dist[i][k] + dist[k][j];
                    if (dist[i][k] != Integer.MAX_VALUE &&
                            dist[k][j] != Integer.MAX_VALUE && distRes < dist[i][j]) {
                        dist[i][j] = distRes;
                        //借k节点过来的
                        path[i][j] = graph.get(k);
                    }
                }
            }
//            print(dist);
        }
        print(dist);
        print(path);
    }

    public static void print(int[][] dist) {
        System.out.println("-------------");
        for (int[] row : dist) {
            System.out.println(Arrays.stream(row)
                    .boxed()
                    .map(x -> x == Integer.MAX_VALUE ? "INF" : String.valueOf(x))
                    .map(s -> String.format("%2s", s))
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }

    public static void print(Vertex[][] dist) {
        System.out.println("-------------");
        for (Vertex[] row : dist) {
            System.out.println(Arrays.stream(row)
                    .map(x -> x != null ? x.name : "null")
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }
}
